package com.dong.arithmetic.tree;

/**
 * 后序遍历：左--->右--->根
 *
 * @author jianyang206881
 * @date 2018/7/23
 */
public class LRD extends CreateTree {
    private TreeNote treeNote;

    public static void main(String[] args) {
        LRD ldr = new LRD();
        TreeNote treeNote = ldr.create(14);

        ldr.traversal(treeNote, null);
        System.out.println("\n");

        ldr.traversal(treeNote, 2);
        System.out.println("\ntraversal: " + ldr.treeNote.getValue());

        TreeNote nextNote = ldr.next(ldr.treeNote);
        System.out.println("\nnext: " + (nextNote == null ? null : nextNote.getValue()));
    }

    /**
     * 返回下一个节点
     *
     * @param treeNote 当前节点
     * @return 下一个节点
     */
    private TreeNote next(TreeNote treeNote) {
        TreeNote parentNote = treeNote.getParent();

        // 该节点是root节点
        if (parentNote == null) {
            return null;
        }

        // 该节点是左节点，取兄弟节点的最终左节点
        if (treeNote.equals(parentNote.getLeft())) {
            TreeNote rightNote = parentNote.getRight();

            // 没有兄弟节点，父节点就是下一节点
            if (rightNote == null) {
                return parentNote;
            }

            // 取兄弟节点的最终叶子节点，优先左节点，然后右节点
            return finallyLeftRightNote(rightNote);
        }

        // 该节点是右节点
        return parentNote;
    }

    private TreeNote finallyLeftRightNote(TreeNote treeNote) {
        TreeNote leftNote = treeNote.getLeft();

        if (leftNote == null) {
            TreeNote rightNote = treeNote.getRight();

            // 取叶子节点的右节点
            if (rightNote != null) {
                return rightNote;
            }

            // 取当前节点
            return treeNote;
        } else {
            return this.finallyLeftRightNote(leftNote);
        }
    }

    /**
     * 遍历并返回指定节点
     *
     * @param treeNote 数
     * @param value    节点值
     */
    private void traversal(TreeNote treeNote, Integer value) {
        if (value != null && value.equals(treeNote.getValue())) {
            this.treeNote = treeNote;
            return;
        }
        if (this.treeNote != null) {
            return;
        }

        if (treeNote.getLeft() != null) {
            this.traversal(treeNote.getLeft(), value);
        }

        if (treeNote.getRight() != null) {
            this.traversal(treeNote.getRight(), value);
        }

        System.out.print(treeNote.getValue() + " ");
    }
}
